package com.datastructure2.array;

import com.sun.corba.se.spi.orbutil.fsm.FSM;
import com.sun.xml.internal.messaging.saaj.soap.impl.HeaderImpl;
import javafx.scene.chart.Chart;
import sun.misc.MetaIndex;

import java.awt.*;
import java.lang.reflect.Member;
import java.net.Inet4Address;
import java.nio.charset.Charset;
import java.util.*;
import java.util.List;

/**
 * @author: 临晖
 * @date: 2023/12/17
 * @description:
 */
public class Solution {


    /**
     * 704. 二分查找
     * 简单
     * 1.5K
     * 相关企业
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 示例 1:
     * 输入: nums = [-1,0,3,5,9,12], target = 9
     * 输出: 4
     * 解释: 9 出现在 nums 中并且下标为 4
     * 示例 2:
     * 输入: nums = [-1,0,3,5,9,12], target = 2
     * 输出: -1
     * 解释: 2 不存在 nums 中因此返回 -1
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        int first = 0;
        int last = nums.length - 1;

        while (first <= last) {
            int mid = (first + last) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                last = mid - 1;
            } else {
                first = mid + 1;
            }
        }
        return -1;
    }


    /**
     * 35. 搜索插入位置
     * 简单
     * 2.2K
     * 相关企业
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * 示例 1:
     * 输入: nums = [1,3,5,6], target = 5
     * 输出: 2
     * 示例 2:
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     * 示例 3:
     * 输入: nums = [1,3,5,6], target = 7
     * 输出: 4
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mind = (left + right) / 2;
            if (nums[mind] == target) {
                return mind;
            } else if (nums[mind] > target) {
                right = mind - 1;
            } else {
                left = mind + 1;
            }
        }

        return right + 1;

    }


    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 中等
     * 2.6K
     * 相关企业
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     * 示例 1：
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);

        if (leftBorder == -2 || rightBorder == -2) {
            return new int[]{-1, -1};
        }

        if (rightBorder - leftBorder > 1) {
            return new int[]{leftBorder + 1, rightBorder - 1};
        }

        return new int[]{-1, -1};
    }


    public int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;
        while (left <= right) {
            int mind = (right + left) / 2;

            if (nums[mind] < target) {
                left = mind + 1;
            } else {
                right = mind - 1;
                leftBorder = right;
            }
        }

        return leftBorder;
    }

    public int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;

        while (left <= right) {
            int mind = (right + left) / 2;

            if (nums[mind] <= target) {

                left = mind + 1;
                rightBorder = left;
            } else {
                right = mind - 1;
            }
        }
        return rightBorder;
    }


    /**
     * 69. x 的平方根
     * 提示
     * 简单
     * 1.5K
     * 相关企业
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int left = 0;
        int right = x / 2 + 1;

        while (left <= right) {
            int middle = (left + right) / 2;
            if ((long) middle * middle == x) {
                return middle;
            } else if ((long) middle * middle > x) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return right;
    }


    /**
     * 27. 移除元素
     * 提示
     * 简单
     * 2.1K
     * 相关企业
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     * 说明:
     * 为什么返回数值是整数，但输出的答案是数组呢?
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     * 你可以想象内部操作如下:
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int index = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[index] = nums[i];
                index++;
            }
        }

        return index + 1;
    }


    /**
     * 26. 删除有序数组中的重复项
     * 提示
     * 简单
     * 3.4K
     * 相关企业
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = 1;
        for (; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }

        return slow;
    }


    /**
     * 283. 移动零
     * 提示
     * 简单
     * 2.3K
     * 相关企业
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * 示例 1:
     * 输入: nums = [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 示例 2:
     * <p>
     * 输入: nums = [0]
     * 输出: [0]
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int slow = 0;
        int fast = 0;

        for (; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }


        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }


    }


    /**
     * 844. 比较含退格的字符串
     * 简单
     * 703
     * 相关企业
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空。
     * <p>
     * 示例 1：
     * 输入：s = "ab#c", t = "ad#c"
     * 输出：true
     * 解释：s 和 t 都会变成 "ac"。
     * 示例 2：
     * 输入：s = "ab##", t = "c#d#"
     * 输出：true
     * 解释：s 和 t 都会变成 ""。
     * 示例 3：
     * 输入：s = "a#c", t = "b"
     * 输出：false
     * 解释：s 会变成 "c"，但 t 仍然是 "b"。
     * 提示：
     * 1 <= s.length, t.length <= 200
     * s 和 t 只含有小写字母以及字符 '#'
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean backspaceCompare(String s, String t) {
        int skipS = 0;      //记录退格个数
        int skipT = 0;

        int indexS = s.length() - 1;     //记录下标
        int indexT = t.length() - 1;


        while (indexS >= 0 || indexT >= 0) {          //如果有一个
            char charS = ' ';
            char charT = ' ';
            while (indexS >= 0) {
                charS = s.charAt(indexS);
                if (charS == '#') {
                    skipS++;
                    indexS--;
                } else if (skipS > 0 && charS != '#') {
                    skipS--;
                    indexS--;
                } else {
                    break;
                }

            }


            while (indexT >= 0) {
                charT = t.charAt(indexT);

                if (charT == '#') {
                    skipT++;
                    indexT--;
                } else if (charT != '#' && skipT > 0) {
                    skipT--;
                    indexT--;
                } else {
                    break;
                }
            }


            //如果有一个已经循环完毕
            if (indexS < 0 || indexT < 0) {
                if (indexS < 0 && indexT < 0) {
                    return true;
                }
                return false;
            }

            //如果字符相等，直接false
            if (charT != charS) {
                return false;
            }

            //如果都没有循环完毕，且当前字母相等
            indexS--;
            indexT--;


        }

        return false;

    }


    /**
     * 977. 有序数组的平方
     * 简单
     * 938
     * 相关企业
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * 示例 1：
     * 输入：nums = [-4,-1,0,3,10]
     * 输出：[0,1,9,16,100]
     * 解释：平方后，数组变为 [16,1,0,9,100]
     * 排序后，数组变为 [0,1,9,16,100]
     * 示例 2：
     * 输入：nums = [-7,-3,2,3,11]
     * 输出：[4,9,9,49,121]
     *
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int size = nums.length;
        int left = 0;
        int right = size - 1;

        int[] res = new int[size];

        while (left <= right) {
            if (nums[left] + nums[right] > 0) {
                res[--size] = nums[right] * nums[right];
                right--;
            } else {
                res[--size] = nums[left] * nums[left];
                left++;
            }

        }

        return res;
    }


    /**
     *
     *209. 长度最小的子数组
     * 中等
     * 2K
     * 相关企业
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * 示例 1：
     * 输入：target = 7, nums = [2,3,1,2,4,3]
     * 输出：2
     * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
     * 示例 2：
     * 输入：target = 4, nums = [1,4,4]
     * 输出：1
     * 示例 3：
     * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
     * 输出：0
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int count = 0;
        int res = Integer.MAX_VALUE;

        int slow = 0;
        int fast = 0;
        int sum = 0;

        for (; fast < nums.length; fast++) {
            sum += nums[fast];

            while (sum >= target) {
                res = Math.min(res, fast - slow + 1);
                sum -= nums[slow];
                slow++;
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }


    /**
     *
     * 904. 水果成篮
     * 中等
     * 593
     * 相关企业
     * 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
     * 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
     * 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
     * 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
     * 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
     * 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
     * 示例 1：
     * 输入：fruits = [1,2,1]
     * 输出：3
     * 解释：可以采摘全部 3 棵树。
     * 示例 2：
     * 输入：fruits = [0,1,2,2]
     * 输出：3
     * 解释：可以采摘 [1,2,2] 这三棵树。
     * 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
     * 示例 3：
     * 输入：fruits = [1,2,3,2,2]
     * 输出：4
     * 解释：可以采摘 [2,3,2,2] 这四棵树。
     * 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
     * 示例 4：
     * 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
     * 输出：5
     * 解释：可以采摘 [1,2,1,1,2] 这五棵树。
     *
     * @param fruits
     * @return
     */
    public static int totalFruit(int[] fruits) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int slow = 0;
        int res = 0;
        int count  = 0;
        for (int i = 0; i < fruits.length; i++) {
            map.put(fruits[i], map.getOrDefault(fruits[i], 0) + 1);
            count++;
            while (map.size() > 2) {
                Integer key = map.get(fruits[slow]);
                key--;
                if (key == 0) {
                    map.remove(fruits[slow]);
                } else {
                    map.put(fruits[slow], key);
                }
                slow++;
                count--;
            }
            res = Math.max(res, count);
        }
        return res;

    }


    /**
     *
     * 76. 最小覆盖子串
     * 提示
     * 困难
     * 2.8K
     * 相关企业
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * 示例 1：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
     * 示例 2：
     * 输入：s = "a", t = "a"
     * 输出："a"
     * 解释：整个字符串 s 是最小覆盖子串。
     * 示例 3:
     *
     * 输入: s = "a", t = "aa"
     * 输出: ""
     * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
     * 因此没有符合条件的子字符串，返回空字符串。
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {

        if (s.length() < t.length()) {
            return "";
        }

        HashMap<Character, Integer> mapT = new HashMap<>();
        HashMap<Character, Integer> mapS = new HashMap<>();

        //将t中的字符存入mapT
        for (int i = 0; i < t.length(); i++) {
            mapT.put(t.charAt(i), mapT.getOrDefault(t.charAt(i), 0) + 1);
        }

        //开始
        int slow = 0;
        int fast = 0;
        String res = "";
        boolean flag = false;

        for (; fast < s.length(); fast++) {
            char op = s.charAt(fast);

            mapS.put(op, mapS.getOrDefault(op, 0) + 1);     //存入mapS

            while (check(mapS, mapT)) {
                if (!flag) {
                    res = s.substring(slow, fast + 1);
                    flag = true;
                }
                res = (fast - slow + 1) < res.length() ? s.substring(slow, fast + 1) : res;
                char op1 = s.charAt(slow);
                Integer value = mapS.get(op1);
                value--;
                if (value == 0) {
                    mapS.remove(op1);
                } else {
                    mapS.put(op1, value);
                }
                slow++;
            }


        }

        return res;
    }


    /**
     * 俩个map集合对比，看mapS是否包含mapT
     *
     * mapS中包含所有mapT中的key
     * mapS中的value 大于等于 mapT中的value
     *
     * @param mapS
     * @param mapT
     * @return
     */
    public boolean check(Map<Character, Integer> mapS, Map<Character, Integer> mapT) {
        Set<Map.Entry<Character, Integer>> entrys = mapT.entrySet();

        for (Map.Entry<Character, Integer> entry : entrys)  {
            if (!mapS.containsKey(entry.getKey())) {        //mapS中包含所有mapT中的key
                return false;
            } else {
                Integer value = mapS.get(entry.getKey());
                if (value < entry.getValue()) {     //mapS中的value 大于等于 mapT中的value
                    return false;
                }
            }
        }

        return true;
    }


    /**
     *
     * 59. 螺旋矩阵 II
     * 中等
     * 1.2K
     * 相关企业
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     *
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];

        int x = 0;
        int y = 0;
        int offset = 1;
        int count = 1;

        int i = 0;
        int j = 0;
        for (int num = 0; num < n / 2; num++) {         //循环圈数

            //上
            for (j = y; j < n - offset; j++) {       //12
                res[x][j] = count++;
            }
            //右
            for (i = x; i < n - offset; i++) {
                res[i][j] = count++;
            }
            //下
            for (; j > y; j--) {
                res[i][j] = count++;
            }

            //左
            for (; i > x; i--) {
                res[i][j] = count++;
            }

            x++;
            y++;
            offset++;

        }

        if (n % 2 == 1) {
            res[n / 2][n / 2] = count;
        }

        return res;
    }


    /**
     *
     * 54. 螺旋矩阵
     * 提示
     * 中等
     * 1.6K
     * 相关企业
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     *
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        //y
        int left = 0;
        int right = n - 1;

        //x
        int hight = 0;
        int low = m - 1;

        while (true) {
            int i;
            int j;

            //上
            for (j = left; j <= right; j++ ) {
                list.add(matrix[hight][j]);
            }

            if (++hight > low) {
                break;
            }
            //右
            for (i = hight; i <= low; i++) {
                list.add(matrix[i][right]);
            }

            if (--right < left) {
                break;
            }



            //下
            for (j = right; j >= left; j--) {
                list.add(matrix[low][j]);
            }

            if (--low < hight) {
                break;
            }
            //左
            for (i = low; i >= hight; i--) {
                list.add(matrix[i][left]);
            }

            if (++left > right) {
                break;
            }

        }

        return list;

    }


    /**
     *
     *LCR 146. 螺旋遍历二维数组
     * 简单
     * 594
     * 相关企业
     * 给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
     * 螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
     * 示例 1：
     * 输入：array = [[1,2,3],[8,9,4],[7,6,5]]
     * 输出：[1,2,3,4,5,6,7,8,9]
     * 示例 2：
     * 输入：array  = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
     * 输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
     *
     * @param matrix
     * @return
     */
    public static int[] spiralArray(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[]{};
        }
        int m = matrix.length;      //m行  y
        int n = matrix[0].length;       //n列 x

        int[] array = new int[m * n];
        //y
        int left = 0;
        int right = n - 1;
        //x
        int first = 0;
        int last = m - 1;

        //
        int count = 0;
        while (true) {
            //上
            for (int i = left; i <= right; i++) {
                array[count++] = matrix[first][i];
            }

            if (++first > last) {
                break;
            }
            //右
            for (int j = first; j <= last; j++) {
                array[count++] = matrix[j][right];
            }

            if (--right < left) {
                break;
            }


            //下
            for (int i = right; i >= left; i--) {
                array[count++] = matrix[last][i];
            }

            if (--last < first) {
                break;
            }

            //左
            for (int j = last; j >= first; j--) {
                array[count++] = matrix[j][left];
            }

            if (++left > right) {
                break;
            }

        }
        return array;

    }



    public static void main(String[] args) {
        Solution so = new Solution();
        so.generateMatrix(4);
    }


}
